package dynamicProgramming.knapsack;

/**
 * @author zxc
 * @date 2023/01/27 10:17
 **/

import java.util.Arrays;

/**
 * 题目 ：最少的硬币数量
 * 题目详述 ：
 * 给定不同面额的硬币 coins 和一个总金额 amount。
 * 编写一个函数来计算可以凑成总金额所需的最少的硬币个数。
 * 如果没有任何一种硬币组合能组成总金额，返回-1。
 * 你可以认为每种硬币的数量是无限的。
 *
 * 提示：
 *
 * 1 <= coins.length <= 12
 * 1 <= coins[i] <= 231 - 1
 * 0 <= amount <= 104
 */
public class CoinChange {
    /**
     * 思路 ：
     * 状态转移方程 ：
     * 假设f(i,j)为前i中硬币中拼凑出总金额为j的最少硬币个数
     * （1）若是使用k个第i种硬币的话，则f(i,j) = f(i-1,j-k*coins[i-1]) + k
     * （2）若是不适用第i种硬币的话，则f(i,j) = f(i--1,j);
     * 综上所述:
     * ===> f(i,j) = min(f(i-1,j) , f(i-1,j-k*coins[i-1]) + k)
     * @param coins
     * @param amount
     * @return
     */
    public int coinChange(int[] coins, int amount) {
        int len = coins.length;

        // 状态转移方程 ：f(i,j) = min(f(i-1,j) , f(i-1,j-k*coins[i-1]) + k)
        /**
         * temp二维数组中 ：
         * 行所存储的是，目标总额的取值范围为[0,amount];
         * 列所存储的是，正在遍历的coins数组中元素;
         * 需要注意的是，temp[i][0]所代表的是 j == 0的情况，其值必然为0;
         */
        int[][] temp = new int[2][amount + 1];
        // 每个硬币的面额必然 >= 1,
        // ===>需要凑成总额大小为amount，即硬币的数目必然是 <= amount;
        Arrays.fill(temp[0] , amount + 1);
        Arrays.fill(temp[1] , amount + 1);
        // 特殊情况 ：
        // 即，当j == 0 && i >= 0时，也是只需要拿出0个硬币即可;
        // ===> 即，只要j == 0的情况下，必然只需要拿出0个硬币即可;
        temp[0][0] = 0;
        temp[1][0] = 0;

        // 由于二维数组temp中行/列所存储的值，需要对其进行遍历，同时对于二维数组temp进行赋值
        for(int i = 0; i < len ; i++){
            for(int j = 1; j <= amount ; j++){
                // 无论是否选择将第i个元素加入到硬币中，都需要使得其等于f(i-1,j)
                temp[(i + 1) % 2][j] = temp[i % 2][j];
                for(int k = 1; k * coins[i] <= j; k++){
                    // for循环 ：遍历变量k的所以可能情况;
                    // 循环结束条件 ：目标值amount < k.coins[i];
                    temp[(i + 1) % 2][j] = Math.min(temp[(i + 1) % 2][j], temp[i % 2][j - k * coins[i]] + k);
                }
            }
        }
        return temp[len % 2][amount] > amount ? -1 : temp[len % 2][amount];
    }
}
